Search Results

Documents authored by Martínez, Conrado

Document
DOI: 10.4230/LIPIcs.AofA.2022.8
Partial Match Queries in Quad- K-d Trees

Authors: Amalia Duch and Conrado Martínez

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
Quad-K-d trees [Bereckzy et al., 2014] are a generalization of several well-known hierarchical K-dimensional data structures. They were introduced to provide a unified framework for the analysis of associative queries and to investigate the trade-offs between the cost of different operations and the memory needs (each node of a quad-K-d tree has arity 2^m for some m, 1 ≤ m ≤ K). Indeed, we consider here partial match - one of the fundamental associative queries - for several families of quad-K-d trees including, among others, relaxed K-d trees and quadtrees. In particular, we prove that the expected cost of a random partial match P̂_n that has s out of K specified coordinates in a random quad-K-d tree of size n is P̂_n ∼ β⋅ n^α where α and β are constants given in terms of K and s as well as additional parameters that characterize the specific family of quad-K-d trees under consideration. Additionally, we derive a precise asymptotic estimate for the main order term of P_{n,𝐪} - the expected cost of a fixed partial match in a random quad-K-d tree of size n. The techniques and procedures used to derive the mentioned costs extend those already successfully applied to derive analogous results in quadtrees and relaxed K-d trees; our results show that the previous results are just particular cases, and states the validity of the conjecture made in [Duch et al., 2016] to a wider variety of multidimensional data structures.
Cite as

Amalia Duch and Conrado Martínez. Partial Match Queries in Quad- K-d Trees. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{duch_et_al:LIPIcs.AofA.2022.8,
  author =	{Duch, Amalia and Mart{\'\i}nez, Conrado},
  title =	{{Partial Match Queries in Quad- K-d Trees}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.8},
  URN =		{urn:nbn:de:0030-drops-160949},
  doi =		{10.4230/LIPIcs.AofA.2022.8},
  annote =	{Keywords: Quadtree, Partial match queries, Associative queries, Multidimensional search, Analysis of algorithms}
}
Document
DOI: 10.4230/LIPIcs.AofA.2022.12
Affirmative Sampling: Theory and Applications

Authors: Jérémie Lumbroso and Conrado Martínez

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
Affirmative Sampling is a practical and efficient novel algorithm to obtain random samples of distinct elements from a data stream. Its most salient feature is that the size S of the sample will, on expectation, grow with the (unknown) number n of distinct elements in the data stream. As any distinct element has the same probability to be sampled, and the sample size is greater when the "diversity" (the number of distinct elements) is greater, the samples that Affirmative Sampling delivers are more representative than those produced by any scheme where the sample size is fixed a priori - hence its name. Our algorithm is straightforward to implement, and several implementations already exist.
Cite as

Jérémie Lumbroso and Conrado Martínez. Affirmative Sampling: Theory and Applications. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lumbroso_et_al:LIPIcs.AofA.2022.12,
  author =	{Lumbroso, J\'{e}r\'{e}mie and Mart{\'\i}nez, Conrado},
  title =	{{Affirmative Sampling: Theory and Applications}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{12:1--12:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.12},
  URN =		{urn:nbn:de:0030-drops-160987},
  doi =		{10.4230/LIPIcs.AofA.2022.12},
  annote =	{Keywords: Data streams, Distinct sampling, Random sampling, Cardinality estimation, Analysis of algorithms}
}
Document
DOI: 10.4230/LIPIcs.AofA.2018.20
Fixed Partial Match Queries in Quadtrees

Authors: Amalia Duch, Gustavo Lau, and Conrado Martínez

Published in: LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Abstract
Several recent papers in the literature have addressed the analysis of the cost P_{n,q} of partial match search for a given fixed query q - that has s out of K specified coordinates - in different multidimensional data structures. Indeed, detailed asymptotic estimates for the main term in the expected cost P_{n,q} = E {P_{n,q}} in standard and relaxed K-d trees are known (for any dimension K and any number s of specified coordinates), as well as stronger distributional results on P_{n,q} for standard 2-d trees and 2-dimensional quadtrees. In this work we derive a precise asymptotic estimate for the main order term of P_{n,q} in quadtrees, for any values of K and s, 0 < s < K, under the assumption that the limit of P_{n,q}/n^alpha when n -> infty exists, where alpha is the exponent of n in the expected cost of a random partial match query with s specified coordinates in a random K-dimensional quadtree.
Cite as

Amalia Duch, Gustavo Lau, and Conrado Martínez. Fixed Partial Match Queries in Quadtrees. In 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 110, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{duch_et_al:LIPIcs.AofA.2018.20,
  author =	{Duch, Amalia and Lau, Gustavo and Mart{\'\i}nez, Conrado},
  title =	{{Fixed Partial Match Queries in Quadtrees}},
  booktitle =	{29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-078-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{110},
  editor =	{Fill, James Allen and Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.20},
  URN =		{urn:nbn:de:0030-drops-89136},
  doi =		{10.4230/LIPIcs.AofA.2018.20},
  annote =	{Keywords: Quadtree, Partial match queries, Associative queries, Multidimensional search, Analysis of algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact